class CircularDoublyLinkedList:
    class _Node:
        def __init__(self, data, prev, next):
            self._data = data
            self._prev = prev
            self._next = next

    def __init__(self):
        self._head = None
        self._size = 0
    
    def __repr__(self):
        if self.is_empty():
            return "None"
        
        nodes = []
        current = self._head
        for _ in range(self._size):
            nodes.append(current._data)
            current = current._next
        nodes.append(f"<-> (back to {self._head._data})")
        return " <-> ".join(nodes)
    
    def __len__(self):
        return self._size
    
    def is_empty(self):
        return self._size == 0

    def get_head(self):
        return self._head._data if self._head is not None else 'Empty'
    
    def get_tail(self):
        return self._head._prev._data if self._head is not None else 'Empty'

    def add_tail(self, e):
        """
        Add an element to the back of the tail
        """
        newest = self._Node(e, None, None)
        if self.is_empty():
            newest._next = newest
            newest._prev = newest
            self._head = newest
        else:
            tail = self._head._prev
            newest._next = self._head
            newest._prev = tail
            tail._next = newest
            self._head._prev = newest
        self._size += 1

    def pop_tail(self):
        """
        Remove and return the last element
        """
        if self.is_empty():
            raise Empty("It's Empty")
        
        tail = self._head._prev
        answer = tail._data
        
        if self._size == 1:
            self._head = None
        else:
            new_tail = tail._prev
            new_tail._next = self._head
            self._head._prev = new_tail
        self._size -= 1
        return answer
    
    def pop_head(self):
        """
        Remove and return the first element
        """
        if self.is_empty():
            raise Empty("It's Empty")
        
        answer = self._head._data
        
        if self._size == 1:
            self._head = None
        else:
            tail = self._head._prev
            new_head = self._head._next
            tail._next = new_head
            new_head._prev = tail
            self._head = new_head
        self._size -= 1
        return answer
    
    def add_head(self, e):
        """
        Add an element to the front of the head
        """
        newest = self._Node(e, None, None)
        if self.is_empty():
            newest._next = newest
            newest._prev = newest
            self._head = newest
        else:
            tail = self._head._prev
            newest._next = self._head
            newest._prev = tail
            tail._next = newest
            self._head._prev = newest
            self._head = newest
        self._size += 1
    
    def search(self, e):
        """
        Search for an element in the linked list
        """
        if self.is_empty():
            return False
        
        current = self._head
        for _ in range(self._size):
            if current._data == e:
                return True
            current = current._next
        return False
    
    def rotate_forward(self):
        """
        Rotate the list forward: move head to the next node
        """
        if not self.is_empty() and self._size > 1:
            self._head = self._head._next
    
    def rotate_backward(self):
        """
        Rotate the list backward: move head to the previous node
        """
        if not self.is_empty() and self._size > 1:
            self._head = self._head._prev
    
    def reverse_repr(self):
        """
        Return a string representation traversing backward from tail
        """
        if self.is_empty():
            return "None"
        
        nodes = []
        current = self._head._prev  # Start from tail
        for _ in range(self._size):
            nodes.append(current._data)
            current = current._prev
        nodes.append(f"<-> (back to {self._head._prev._data})")
        return " <-> ".join(nodes)
    
    def get_all_nodes_forward(self):
        """
        Return a list of all node data in forward order
        """
        if self.is_empty():
            return []
        
        nodes = []
        current = self._head
        for _ in range(self._size):
            nodes.append(current._data)
            current = current._next
        return nodes
    
    def get_all_nodes_backward(self):
        """
        Return a list of all node data in backward order
        """
        if self.is_empty():
            return []
        
        nodes = []
        current = self._head._prev  # Start from tail
        for _ in range(self._size):
            nodes.append(current._data)
            current = current._prev
        return nodes


class Empty(Exception):
    def __init__(self, *args):
        super().__init__(*args)


if __name__ == '__main__':
    cdll = CircularDoublyLinkedList()

    cdll.add_tail('pomme')
    cdll.add_tail('banana')
    cdll.add_tail('orange')
    cdll.add_tail('kiwi')
    print(f"Size: {cdll._size}")
    print(f"Forward: {cdll}")
    print(f"Backward: {cdll.reverse_repr()}")
    print(f"Head: {cdll.get_head()}")
    print(f"Tail: {cdll.get_tail()}")
    
    print(f"\nPopping head: {cdll.pop_head()}")
    print(f"After pop_head: {cdll}")
    
    print(f"\nPopping tail: {cdll.pop_tail()}")
    print(f"After pop_tail: {cdll}")
    
    print(f"\nSearch 'banana': {cdll.search('banana')}")
    print(f"Search 'pomme': {cdll.search('pomme')}")
    
    print(f"\nRotating forward...")
    cdll.rotate_forward()
    print(f"After rotate_forward: {cdll}")
    print(f"New head: {cdll.get_head()}")
    print(f"New tail: {cdll.get_tail()}")
    
    print(f"\nRotating backward...")
    cdll.rotate_backward()
    print(f"After rotate_backward: {cdll}")
    print(f"New head: {cdll.get_head()}")
    
    print(f"\nAdding 'fraise' to head...")
    cdll.add_head('fraise')
    print(f"After add_head: {cdll}")
    
    print(f"\nAll nodes forward: {cdll.get_all_nodes_forward()}")
    print(f"All nodes backward: {cdll.get_all_nodes_backward()}")
    
    print(f"\nAdding 'cerise' to tail...")
    cdll.add_tail('cerise')
    print(f"After add_tail: {cdll}")
